#include <util.h>
#include "qsort.h"

int 
partition(int a[], int p, int r)
{
    int i, j, x;

    /*fprintf(stdout, "start of partition:\n");
    print_a_range(a, p, r);*/
    x = a[r];
    for (i = p-1/*NOTE: p-1, not -1 */, j = p; j < r; j++)
    {
	if (a[j] <= x)
	{
	    swap(&a[++i], &a[j]);
	}
	/*fprintf(stdout, "i(%d), j(%d)\n", i, j);
	print_a_range(a, p, r);*/
    }
    swap(&a[i+1], &a[r]);
    /*fprintf(stdout, "p(%d), r(%d), q(%d)\n", p, r, i+1);
    print_a_range(a, p, r);*/

    return i+1;
}

int 
partition_ex(int a[], int p, int r, int x)
{
    int i;

//    printf("p %d, r %d, x %d\n", p, r, x);
    for (i = p; i <= r; i++)
    {
//        printf("a[%d] %d\n", i, a[i]);
        if (a[i] == x)
        {
            swap(&a[r], &a[i]);
            return partition(a, p, r);
        }
    }
    
    assert(0);
    
    return 0;
}

void 
quicksort(int a[], int p, int r)
{
    int q;

    if (p < r)
    {
	q = partition(a, p, r);
	quicksort(a, p, q-1);
	quicksort(a, q+1, r);
    }
}

void 
quicksort_no_tail_recursion(int a[], int p, int r)
{
    int q;

    while (p < r)
    {
        q = partition(a, p, r);
        quicksort_no_tail_recursion(a, p, q-1);
        p = q + 1;
    }
}
